home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / circuits / irsim-ca.2 / irsim-ca / irsim-cap-9.2 / src / irsim / sched.c < prev    next >
C/C++ Source or Header  |  1993-01-15  |  18KB  |  734 lines
  1. /* 
  2.  *     ********************************************************************* 
  3.  *     * Copyright (C) 1988, 1990 Stanford University.                     * 
  4.  *     * Permission to use, copy, modify, and distribute this              * 
  5.  *     * software and its documentation for any purpose and without        * 
  6.  *     * fee is hereby granted, provided that the above copyright          * 
  7.  *     * notice appear in all copies.  Stanford University                 * 
  8.  *     * makes no representations about the suitability of this            * 
  9.  *     * software for any purpose.  It is provided "as is" without         * 
  10.  *     * express or implied warranty.  Export of this software outside     * 
  11.  *     * of the United States of America may require an export license.    * 
  12.  *     ********************************************************************* 
  13.  */
  14.  
  15. #include <stdio.h>
  16. #include "defs.h"
  17. #include "net.h"
  18. #include "globals.h"
  19. #include "ASSERT.h"
  20.  
  21.  
  22. #define    TSIZE        1024    /* size of event array, must be power of 2 */
  23. #define    TMASK        (TSIZE - 1)
  24.  
  25. typedef struct
  26.   {
  27.     evptr    flink, blink;    /* pointers in doubly-linked list */
  28.   } evhdr;
  29.  
  30.  
  31. public    int    debug = 0;        /* if <>0 print lotsa interesting info */
  32.  
  33. public    long   cur_delta;        /* current simulated time */
  34. public    nptr   cur_node;        /* node that belongs to current event */
  35. public    long   nevent;            /* number of current event */
  36.  
  37. public    evptr  evfree = NULL;        /* list of free event structures */
  38. public    int    npending;        /* number of pending events */
  39.  
  40.  
  41. private    evhdr  ev_array[TSIZE];        /* used as head of doubly-linked lists */
  42.  
  43.  
  44.  
  45. /*
  46.  * Sets the parameter "list" to contain a pointer to the list of pending 
  47.  * events at time "cur_delta + delta".  "end_of_list" contains a pointer to
  48.  * the end of the list. If there are no events at the indicated time "list"
  49.  * is set to NULL.  The function returns 0 if there are no events past the
  50.  * "cur_delta + delta", otherwise it returns the delta at which the next
  51.  * events are found;
  52.  */
  53.  
  54. public int pending_events( delta, list, end_of_list )
  55.   long   delta;
  56.   evptr  *list, *end_of_list;
  57.   {
  58.     evhdr           *hdr;
  59.     register evptr  ev;
  60.  
  61.     *list = NULL;
  62.  
  63.     delta += cur_delta;
  64.     hdr = &ev_array[ delta & TMASK ];
  65.  
  66.     if( hdr->flink == (evptr) hdr or hdr->blink->ntime < delta )
  67.     goto find_next;
  68.  
  69.     for( ev = hdr->flink; ev->ntime < delta; ev = ev->flink );
  70.     if( ev->ntime != delta )
  71.     goto find_next;
  72.  
  73.     *list = ev;
  74.     if( hdr->blink->ntime == ev->ntime )
  75.     *end_of_list = hdr->blink;
  76.     else
  77.       {
  78.     for( delta = ev->ntime; ev->ntime == delta; ev = ev->flink );
  79.     *end_of_list = ev->blink;
  80.       }
  81.  
  82.   find_next:
  83.      {
  84.     register long  i, limit, time;
  85.  
  86.     time = max_time;
  87.     for( i = ++delta, limit = i + TSIZE; i < limit; i++ )
  88.       {
  89.         ev = (evptr) &ev_array[ i & TMASK ];
  90.         if( ev != ev->flink )
  91.           {
  92.         if( ev->blink->ntime < delta )
  93.             continue;
  94.         for( ev = ev->flink; ev->ntime < delta; ev = ev->flink );
  95.         if( ev->ntime < limit )
  96.           {
  97.             time = ev->ntime;
  98.             break;
  99.           }
  100.         else if( ev->flink->ntime < time )
  101.             time = ev->flink->ntime;
  102.           }
  103.       }
  104.     delta = ( time != max_time ) ? time - cur_delta : 0;
  105.       }
  106.  
  107.     return( delta );
  108.   }
  109.  
  110.  
  111. /*
  112.  * find the next event to be processed by scanning event wheel.  Return
  113.  * the list of events to be processed at this time, removing it first
  114.  * from the time wheel.
  115.  */
  116. public evptr get_next_event( stop_time )
  117.   long  stop_time;
  118.   {
  119.     register evptr  event;
  120.     register long   i, limit, time;
  121.  
  122.     if( npending == 0 )
  123.     return( NULL );
  124.  
  125.     time = max_time;
  126.     for( i = cur_delta, limit = i + TSIZE; i < limit; i++ )
  127.       {
  128.     event = (evptr) &ev_array[ i & TMASK ];
  129.     if( event != event->flink )
  130.       {
  131.         if( event->flink->ntime < limit )        /* common case */
  132.         goto found;
  133.         if( event->flink->ntime < time )
  134.         time = event->flink->ntime;
  135.       }
  136.       }
  137.  
  138.     if( time != max_time )
  139.     event = (evptr) &ev_array[ time & TMASK ];
  140.     else
  141.       {
  142.     lprintf( stderr, "*** internal error: no events but npending set\n" );
  143.     return( NULL );
  144.       }
  145.  
  146.   found:
  147.       {
  148.     evptr  evlist = event->flink;
  149.  
  150.     time = evlist->ntime;
  151.  
  152.     if( time >= stop_time )
  153.         return( NULL );
  154.  
  155.     /* sanity check for incremental simulation mostly */
  156.     ASSERT( time >= cur_delta )
  157.       {
  158.         lprintf( stderr, "time moving back %d -> %d\n", cur_delta,
  159.          evlist->ntime );
  160.       }
  161.  
  162.     cur_delta = time;            /* advance simulation time */
  163.  
  164.     if( event->blink->ntime != time )    /* check tail of list */
  165.       {
  166.         do
  167.         event = event->flink;
  168.         while( event->ntime == time );
  169.  
  170.         event = event->blink;        /* grab part of the list */
  171.         evlist->blink->flink = event->flink;
  172.         event->flink->blink = evlist->blink;
  173.         evlist->blink = event;
  174.         event->flink = NULL;
  175.       }
  176.     else
  177.       {
  178.         event = evlist->blink;        /* grab the entire list */
  179.         event->blink->flink = NULL;
  180.         evlist->blink = event->blink;
  181.         event->flink = event->blink = (evptr) event;
  182.       }
  183.     return( evlist );
  184.       }
  185.   }
  186.  
  187.  
  188. /* remove event from node's list of pending events */
  189. public
  190. #define free_from_node( ev, nd )                    \
  191.   {                                    \
  192.     if( (nd)->events == (ev) )                        \
  193.     (nd)->events = (ev)->nlink;                    \
  194.     else                                \
  195.       {                                    \
  196.     register evptr  evp;                        \
  197.     for( evp = (nd)->events; evp->nlink != (ev); evp = evp->nlink );\
  198.     evp->nlink = (ev)->nlink;                    \
  199.       }                                    \
  200.   }
  201.  
  202.  
  203. public
  204. #define    FreeEventList( L )    (L)->blink->flink = evfree, evfree = (L)
  205.  
  206.  
  207. /*
  208.  * remove event from all structures it belongs to and return it to free pool
  209.  */
  210. public void free_event( event )
  211.   register evptr  event;
  212.   {
  213.     /* unhook from doubly-linked event list */
  214.     event->blink->flink = event->flink;
  215.     event->flink->blink = event->blink;
  216.     npending -= 1;
  217.  
  218.     /* add to free storage pool */
  219.     event->flink = evfree;
  220.     evfree = event;
  221.  
  222.     free_from_node( event, event->enode );
  223.   }
  224.  
  225. /* get event structure.  Allocate a bunch more if we've run out. */
  226. #define NEW_EVENT( NEW )                    \
  227.   {                                \
  228.     if( ((NEW) = evfree) == NULL )                \
  229.     (NEW) = (evptr) MallocList( sizeof( struct Event ), 1 );\
  230.     evfree = (NEW)->flink;                    \
  231.   }
  232.  
  233.  
  234. /*
  235.  * Add an event to event list, specifying transition delay and new value.
  236.  * 0 delay transitions are converted into unit delay transitions (0.1 ns).
  237.  */
  238. public void enqueue_event( n, newvalue, delta, rtime )
  239.   register nptr  n;
  240.   long           delta, rtime;
  241.   {
  242.     register evptr  marker, new;
  243.     register long   etime;
  244.  
  245.     /* check against numerical errors from new_val routines */
  246.     ASSERT( delta > 0 and delta < 60000 )
  247.       {
  248.     lprintf( stderr, "bad event @ %.1fns: %s ,delay=%ddeltas\n",
  249.       d2ns( cur_delta ), pnode( n ), delta );
  250.     delta = rtime = 1;
  251.       }
  252.  
  253.     NEW_EVENT( new );
  254.  
  255.     /* remember facts about this event */
  256.     new->ntime = etime = cur_delta + delta;
  257.     new->rtime = rtime;
  258.     new->enode = n;
  259.     new->p.cause = cur_node;
  260.     new->delay = delta;
  261.     if( newvalue == DECAY )        /* change value to X here */
  262.       {
  263.     new->eval = X;
  264.     new->type = DECAY_EV;
  265.       }
  266.     else
  267.       {
  268.     new->eval = newvalue;
  269.     new->type = REVAL;        /* for incremental simulation */
  270.       }
  271.  
  272.     /* add the new event to the event list at the appropriate entry
  273.      * in event wheel.  Event lists are kept sorted by increasing
  274.      * event time.
  275.      */
  276.     marker = (evptr) & ev_array[ etime & TMASK ];
  277.  
  278.     /* Check whether we need to insert-sort in the list */
  279.     if( (marker->blink != marker) and (marker->blink->ntime > etime) )
  280.       {
  281.     do { marker = marker->flink; } while( marker->ntime <= etime );
  282.       }
  283.  
  284.     /* insert event right before event pointed to by marker */
  285.     new->flink = marker;
  286.     new->blink = marker->blink;
  287.     marker->blink->flink = new;
  288.     marker->blink = new;
  289.     npending += 1;
  290.  
  291.     /* 
  292.      * thread event onto list of events for this node, keeping it
  293.      * in sorted order
  294.      */
  295.     if( (n->events != NULL) and (n->events->ntime > etime) )
  296.       {
  297.     for( marker = n->events; (marker->nlink != NULL) and
  298.       (marker->nlink->ntime > etime); marker = marker->nlink );
  299.     new->nlink = marker->nlink;
  300.     marker->nlink = new;
  301.       }
  302.     else
  303.       {
  304.     new->nlink = n->events;
  305.     n->events = new;
  306.       }
  307.   }
  308.  
  309.  
  310. /* same as enqueue_event, but assumes 0 delay and rtise/fall time */
  311. public void enqueue_input( n, newvalue )
  312.   register nptr  n;
  313.   {
  314.     register evptr  marker, new;
  315.     register long   etime;
  316.  
  317.     /* Punt any pending events for this node. */
  318.     while( n->events != NULL )
  319.     free_event( n->events );
  320.  
  321.     NEW_EVENT( new );
  322.  
  323.     /* remember facts about this event */
  324.     new->ntime = etime = cur_delta;
  325.     new->rtime = new->delay = 0;
  326.     new->enode = new->p.cause = n;
  327.     new->eval = newvalue;
  328.     new->type = REVAL;            /* anything, doesn't matter */
  329.  
  330.      /* Add new event to HEAD of list at appropriate entry in event wheel */
  331.  
  332.     marker = (evptr) & ev_array[ etime & TMASK ];
  333.     new->flink = marker->flink;
  334.     new->blink = marker;
  335.     marker->flink->blink = new;
  336.     marker->flink = new;
  337.     npending += 1;
  338.  
  339.     /* thread event onto (now empty) list of events for this node */
  340.     new->nlink = NULL;
  341.     n->events = new;
  342.   }
  343.  
  344.  
  345. /*
  346.  * Initialize event structures
  347.  */
  348. public void init_event()
  349.   {
  350.     register int    i;
  351.     register evhdr  *event;
  352.  
  353.     for( i = 0, event = &ev_array[0]; i < TSIZE; i += 1, event += 1 )
  354.       {
  355.     event->flink = event->blink = (evptr) event;
  356.       }
  357.     npending = 0;
  358.     nevent = 0;
  359.   }
  360.  
  361.  
  362. public void PuntEvent( node, ev )
  363.   nptr   node;
  364.   evptr  ev;
  365.   {
  366.     if( node->nflags & WATCHED )
  367.     lprintf( stdout,
  368.       "    punting transition of %s -> %c scheduled for %2.1fns\n",
  369.       node->nname, vchars[ev->eval], d2ns( ev->ntime ) );
  370.  
  371.     ASSERT( node == ev->enode )
  372.       {
  373.     lprintf( stderr, "bad punt @ %d for %s\n", cur_delta, node->nname );
  374.     node->events = NULL;
  375.     return;
  376.       }
  377.  
  378.     if( ev->type != DECAY_EV )        /* don't save punted decay events */
  379.     AddPunted( ev->enode, ev, cur_delta );
  380.     free_event( ev );
  381.   }
  382.  
  383.  
  384. public void requeue_events( evlist, thread )
  385.   evptr  evlist;
  386.   int    thread;
  387.   {
  388.     register long   etime;
  389.     register evptr  ev, next, target;
  390.  
  391.     npending = 0;
  392.     for( ev = evlist; ev != NULL; ev = next )
  393.       {
  394.     next = ev->flink;
  395.  
  396.     npending++;
  397.     etime = ev->ntime;
  398.     target = (evptr) & ev_array[ etime & TMASK ];
  399.  
  400.     if( (target->blink != target) and (target->blink->ntime > etime) )
  401.       {
  402.         do { target = target->flink; } while( target->ntime <= etime );
  403.       }
  404.  
  405.     ev->flink = target;
  406.     ev->blink = target->blink;
  407.     target->blink->flink = ev;
  408.     target->blink = ev;
  409.  
  410.     if( thread )
  411.       {
  412.         register nptr   n = ev->enode;
  413.         register evptr  marker;
  414.  
  415.         if( (n->events != NULL) and (n->events->ntime > etime) )
  416.           {
  417.         for( marker = n->events; (marker->nlink != NULL) and
  418.           (marker->nlink->ntime > etime); marker = marker->nlink );
  419.         ev->nlink = marker->nlink;
  420.         marker->nlink = ev;
  421.           }
  422.         else
  423.           {
  424.         ev->nlink = n->events;
  425.         n->events = ev;
  426.           }
  427.       }
  428.       }
  429.   }
  430.  
  431.     /* Incremental simulation routines */
  432.  
  433. /*
  434.  * Back the event queues up to time 'btime'.  This is the opposite of
  435.  * advancing the simulation time.  Mark all pending events as PENDING,
  436.  * and re-enqueue them according to their creation-time (ntime - delay).
  437.  */
  438. public evptr back_sim_time( btime, is_inc )
  439.   long  btime;
  440.   int   is_inc;
  441.   {
  442.     evptr           tmplist;
  443.     register int    nevents;
  444.     register evptr  ev, next;
  445.     register evhdr  *hdr, *endhdr;
  446.  
  447.     nevents = 0;
  448.     tmplist = NULL;
  449.  
  450.     /* first empty out the time wheel onto the temporary list */
  451.     for( endhdr = &ev_array[ TSIZE ], hdr = ev_array; hdr != endhdr ; hdr++ )
  452.       {
  453.     for( ev = hdr->flink; ev != (evptr) hdr; ev = next )
  454.       {
  455.         next = ev->flink;
  456.  
  457.         ev->blink->flink = ev->flink;    /* remove event */
  458.         ev->flink->blink = ev->blink;
  459.         if( is_inc )
  460.         free_from_node( ev, ev->enode );
  461.  
  462.         if( (not is_inc) and ev->ntime - ev->delay >= btime )
  463.           {
  464.         free_from_node( ev, ev->enode );
  465.         ev->flink = evfree;
  466.         evfree = ev;
  467.           }
  468.         else
  469.           {
  470.         ev->flink = tmplist;        /* move it to tmp list */
  471.         tmplist = ev;
  472.  
  473.         nevents++;
  474.           }
  475.       }
  476.       }
  477.  
  478.     if( not is_inc )
  479.       {
  480.     requeue_events( tmplist, FALSE );
  481.     return( NULL );
  482.       }
  483.  
  484.     if( is_inc != TRUE )    /* only for fault simulation (is_inc == 2) */
  485.       {
  486.     npending = 0;
  487.     return( tmplist );
  488.       }
  489.  
  490.     /* now move the temporary list to the time wheel */
  491.     for( ev = tmplist; ev != NULL; ev = next )
  492.       {
  493.     register long   etime;
  494.     register evptr  target;
  495.  
  496.     next = ev->flink;
  497.  
  498.     ev->ntime -= ev->delay;
  499.     ev->type = PENDING;
  500.     etime = ev->ntime;
  501.     target = (evptr) & ev_array[ etime & TMASK ];
  502.  
  503.     if( (target->blink != target) and (target->blink->ntime > etime) )
  504.       {
  505.         do { target = target->flink; } while( target->ntime <= etime );
  506.       }
  507.  
  508.     ev->flink = target;
  509.     ev->blink = target->blink;
  510.     target->blink->flink = ev;
  511.     target->blink = ev;
  512.       }
  513.  
  514.     npending = nevents;
  515.     return( NULL );
  516.   }
  517.  
  518.  
  519. /*
  520.  * Enqueue event type 'type' form history entry 'hist' for node 'nd'.
  521.  * Note that events with type > THREAD are not threaded onto a node's list
  522.  * of pending events, since we don't want the new_val routines to look at
  523.  * this event, instead we keep track of these events in the c.event event
  524.  * of every node.  Return FALSE if this history entry is the sentinel
  525.  * (last_hist), otherwise return TRUE.
  526.  */
  527. public int EnqueueHist( nd, hist, type )
  528.   nptr  nd;
  529.   hptr  hist;
  530.   int   type;
  531.   {
  532.     register evptr  marker, new;
  533.     register long   etime;
  534.  
  535.     if( hist == last_hist )            /* never queue this up */
  536.       {
  537.     nd->c.event = NULL;
  538.     return( FALSE );
  539.       }
  540.  
  541.     NEW_EVENT( new );
  542.  
  543.     /* remember facts about this event */
  544.     new->ntime = etime = hist->time;
  545.     new->eval = hist->val;
  546.     new->enode = nd;
  547.     new->p.hist = hist;
  548.     if( hist->punt )
  549.       {
  550.     new->delay = hist->t.p.delay;
  551.     new->rtime = hist->t.p.rtime;
  552.       }
  553.     else
  554.       {
  555.     new->delay = hist->t.r.delay;
  556.     new->rtime = hist->t.r.rtime;
  557.       }
  558.  
  559.     marker = (evptr) & ev_array[ etime & TMASK ];
  560.  
  561.     /* Check whether we need to insert-sort in the list */
  562.     if( (marker->blink != marker) and (marker->blink->ntime > etime) )
  563.       {
  564.     do { marker = marker->flink; } while( marker->ntime <= etime );
  565.       }
  566.  
  567.     /* insert event right before event pointed to by marker */
  568.     new->flink = marker;
  569.     new->blink = marker->blink;
  570.     marker->blink->flink = new;
  571.     marker->blink = new;
  572.     npending += 1;
  573.  
  574.     if( hist->inp )
  575.     type |= IS_INPUT;
  576.     else if( new->delay == 0 )
  577.     type |= IS_XINPUT;
  578.     new->type = type;
  579.  
  580.     if( type > THREAD )
  581.       {
  582.     nd->c.event = new;
  583.     return( TRUE );
  584.       }
  585.  
  586.     if( (nd->events != NULL) and (nd->events->ntime > etime) )
  587.       {
  588.     for( marker = nd->events; (marker->nlink != NULL) and
  589.       (marker->nlink->ntime > etime); marker = marker->nlink );
  590.     new->nlink = marker->nlink;
  591.     marker->nlink = new;
  592.       }
  593.     else
  594.       {
  595.     new->nlink = nd->events;
  596.     nd->events = new;
  597.       }
  598.     return( TRUE );
  599.   }
  600.  
  601.  
  602. public void DequeueEvent( nd )
  603.   register nptr nd;
  604.   {
  605.     register evptr  ev;
  606.  
  607.     ev = nd->c.event;
  608.     ev->blink->flink = ev->flink;
  609.     ev->flink->blink = ev->blink;
  610.     ev->flink = evfree;
  611.     evfree = ev;
  612.     nd->c.event = NULL;
  613.  
  614.     npending -= 1;
  615.   }
  616.  
  617.  
  618. public void DelayEvent( ev, delay )
  619.   evptr  ev;
  620.   long   delay;
  621.   {
  622.     register evptr  marker, new;
  623.     register long   etime;
  624.     register nptr   nd;
  625.  
  626.     nd = ev->enode;
  627.     NEW_EVENT( new );
  628.     
  629.     /* remember facts about this event */
  630.     *new = *ev;
  631.     new->delay += delay;
  632.     new->ntime += delay;
  633.  
  634.     etime = new->ntime;
  635.  
  636.     marker = (evptr) & ev_array[ etime & TMASK ];
  637.  
  638.     /* Check whether we need to insert-sort in the list */
  639.     if( (marker->blink != marker) and (marker->blink->ntime > etime) )
  640.       {
  641.     do { marker = marker->flink; } while( marker->ntime <= etime );
  642.       }
  643.  
  644.     /* insert event right before event pointed to by marker */
  645.     new->flink = marker;
  646.     new->blink = marker->blink;
  647.     marker->blink->flink = new;
  648.     marker->blink = new;
  649.     npending += 1;
  650.  
  651.     if( new->type > THREAD )
  652.       {
  653.     nd->c.event = new;
  654.     return;
  655.       }
  656.  
  657.     if( (nd->events != NULL) and (nd->events->ntime > etime) )
  658.       {
  659.     for( marker = nd->events; (marker->nlink != NULL) and
  660.       (marker->nlink->ntime > etime); marker = marker->nlink );
  661.     new->nlink = marker->nlink;
  662.     marker->nlink = new;
  663.       }
  664.     else
  665.       {
  666.     new->nlink = nd->events;
  667.     nd->events = new;
  668.       }
  669.   }
  670.  
  671.  
  672. public evptr EnqueueOther( type, time )
  673.   int   type;
  674.   long  time;
  675.   {
  676.     register evptr  marker, new;
  677.     register long   etime;
  678.  
  679.     NEW_EVENT( new );
  680.  
  681.     new->ntime = etime = time;
  682.     new->type = type;
  683.  
  684.     marker = (evptr) & ev_array[ etime & TMASK ];
  685.  
  686.     /* Check whether we need to insert-sort in the list */
  687.     if( (marker->blink != marker) and (marker->blink->ntime > etime) )
  688.       {
  689.     do { marker = marker->flink; } while( marker->ntime <= etime );
  690.       }
  691.  
  692.     /* insert event right before event pointed to by marker */
  693.     new->flink = marker;
  694.     new->blink = marker->blink;
  695.     marker->blink->flink = new;
  696.     marker->blink = new;
  697.     npending += 1;
  698.     return( new );
  699.   }
  700.  
  701.  
  702. /*
  703.  * Remove any events that may be left from the incremental simulation.
  704.  */
  705. public void rm_inc_events( all )
  706.   int  all;
  707.   {
  708.     register int    i, nevents;
  709.     register evptr  ev, next;
  710.     register evhdr  *hdr, *endhdr;
  711.  
  712.     nevents = 0;
  713.  
  714.     for( endhdr = &ev_array[ TSIZE ], hdr = ev_array; hdr != endhdr; hdr++ )
  715.       {
  716.     for( ev = hdr->flink; ev != (evptr) hdr; ev = next )
  717.       {
  718.         next = ev->flink;
  719.         if( all or ev->type >= THREAD )
  720.           {
  721.         ev->blink->flink = next;        /* remove event */
  722.         ev->flink->blink = ev->blink;
  723.         ev->flink = evfree;
  724.         evfree = ev;
  725.         if( ev->type <= THREAD )
  726.             free_from_node( ev, ev->enode );
  727.           }
  728.         else
  729.         nevents++;
  730.       }
  731.       }
  732.     npending = nevents;
  733.   }
  734.